/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-19 11:14:04
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-19 12:14:00
 * @FilePath: \LeetCode\120.三角形最小路径和.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=120 lang=cpp
 *
 * [120] 三角形最小路径和
 *
 * 方法1：动态规划
 * - 分治算法子问题有重叠
 * - 状态 dp[k] = triangle[i][j], k = i*(i+1)/2 + j：第 k 个元素开始的最小路径
 * - 状态转移方程：dp[i][j] = min{dp[i+1][j], dp[i+1][j+1]} + triangle[i][j]
 */

#include <vector>
#include <iostream>

// @lc code=start
class Solution
{
public:
    int minimumTotal(std::vector<std::vector<int>> &triangle)
    {
        const int deepT = triangle.size();
        const int total = (1 + deepT) * deepT / 2; // 元素总数

        std::vector<int> min_pathsum(total); // dp[k] = triangle[i][j]
        /* 自底向上 初始化最后一行 triangle[deepT-1][0...deepT-1] */
        for (int i = 0; i < deepT; i++)
            min_pathsum[total - deepT + i] = triangle[deepT - 1][i];

        for (int i = deepT - 2; i >= 0; i--)
        {
            /* k = i*(i+1)/2 + j */
            int k0 = i * (i + 1) / 2;       // dp[i][0]
            int k1 = (i + 1) * (i + 2) / 2; // dp[i+1][0]
            for (int j = 0; j <= i; j++)
            {
                min_pathsum[k0 + j] =
                    std::min(min_pathsum[k1 + j],
                             min_pathsum[k1 + j + 1]) +
                    triangle[i][j];
            }
        }

        return min_pathsum[0]; // 自顶向下的最小路径和
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    std::vector<std::vector<int>> triangle = {{-10}}; //{{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
    std::cout << solution.minimumTotal(triangle) << std::endl;
    return 0;
}